删除链表的倒数第N个结点

发表于 | 分类于 |
字数统计: 476 字 | 阅读时长 ≈ 2 分钟

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

 

示例 1：img
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

方法一：虚拟头节点+快慢指针

引用虚拟头节点解决删除头节点的问题

设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

  • 设置虚拟节点 dummyHead 指向 head
  • 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
  • 移动 q，直到 p 与 q 之间相隔的元素个数为 n
  • 同时移动 p 与 q，直到 q 指向的为 NULL
  • 将 p 的下一个节点指向下下个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode fast = dummyHead, slow = dummyHead;
    while(n-- > 0) {
      fast = fast.next;
    }
    while(fast.next != null) {
      slow = slow.next;
      fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummyHead.next;
  }
}

var removeNthFromEnd = function(head, n) {
  if(head === null ||n === 0) return null
  let dummyHead = new ListNode(0)
  dummyHead.next = head
  let fast = dummyHead, slow = dummyHead
  while(n--) {
    fast = fast.next
  }
  while(fast.next) {
    slow = slow.next
    fast = fast.next
  }
  slow.next = slow.next.next
  return dummyHead.next
};

复杂度分析

  • 时间复杂度：O(L)，其中 L是链表的长度。
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：36.6 MB, 在所有 Java 提交中击败了15.98%的用户